package two.chapter_3.c3_4;

import two.chapter_1.c1_3.LinkedQueue;
import two.chapter_1.c1_3.Queue;

/**
 * 线性探测法实现的散列表
 * @param <Key>
 * @param <Value>
 */
public class LinearProbingHashST<Key,Value> implements HashST<Key,Value> {
    private int N;
    private int M;//数组大小
    private Key[]keys;
    private Value[]values;
    public LinearProbingHashST(int capacity){
        M=capacity;
        keys= (Key[]) new Object[M];
        values= (Value[]) new Object[M];
    }
    public LinearProbingHashST(){
       this(16);
    }
    @Override
    public void put(Key key, Value value) {

        if(N>=M/2) resize(2*M);

        int index=hash(key);

        for (;keys[index]!=null;index=(index+1)%M){
            if (keys[index].equals(key)){
                values[index]=value;
                return;
            }
        }
        keys[index]=key;
        values[index]=value;
        N++;
    }

    private void resize(int capacity) {
        LinearProbingHashST<Key,Value> st=new LinearProbingHashST<>(capacity);
        for (int i=0;i<M;i++){
            if (keys[i]!=null)
                st.put(keys[i],values[i]);
        }
        this.keys=st.keys;
        this.values=st.values;
        this.M=st.M;

    }

    @Override
    public Value get(Key key) {
        int index=hash(key);
        for (;keys[index]!=null;index=(index+1)%M){
            if (keys[index].equals(key)){
                return values[index];
            }
        }
        return null;
    }

    @Override
    public void delete(Key key) {
        if (!contains(key)){
            return;
        }
        int i=hash(key);
        while (!key.equals(keys[i])){
            i=(i+1)%M;
        }
        keys[i]=null;
        values[i]=null;
        i=(i+1)%M;
        while (keys[i]!=null){
            Key keyToRedo=keys[i];
            Value valueToRedo=values[i];
            keys[i]=null;
            values[i]=null;
            N--;
            put(keyToRedo,valueToRedo);
            i=(i+1)%M;
        }
        N--;
        if (N>0 && N==M/8) resize(M/2);
    }

    @Override
    public Iterable<Key> keys() {
        Queue<Key> queue=new LinkedQueue<>();
        for (int i=0;i<M;i++){
            if (keys[i]!=null)
                queue.enqueue(keys[i]);
        }
        return queue;
    }

    @Override
    public boolean contains(Key key) {
        return get(key)!=null;
    }

    @Override
    public int hash(Key key) {
        return (key.hashCode()&0x7fffffff)%M;
    }

    @Override
    public boolean isEmpty() {
        return size()==0;
    }

    @Override
    public int size() {
        return N;
    }


}
